#pragma once

#include <algorithm>
#include <vector>

namespace solution_015
{

class Solution {
public:
    std::vector< std::vector<int> > threeSum(std::vector<int>& nums)
    {
        if (nums.size() < 3)
            return { };
        std::sort(nums.begin(), nums.end());

        if (nums.back() < 0)
            return { };
        std::vector< std::vector<int> > tri;
        for (int k = 0, n = nums.size(); k + 2 < n; ++k) {
            if (k > 0 && nums[k] == nums[k-1])
                continue;
            if (nums[k] + nums[k+1] + nums[k+2] > 0)
                break;
            if (nums[k] + nums[n-1] + nums[n-2] < 0)
                continue;

            for (int i = k + 1, j = n - 1; i < j; ) {
                int sum = nums[k] + nums[i] + nums[j];
                if (sum < 0) {
                    while (++i < j && nums[i] == nums[i-1]);
                } else if (sum > 0) {
                    while (i < --j && nums[j] == nums[j+1]);
                } else {
                    tri.push_back({ nums[k], nums[i], nums[j] });
                    while (++i < j && nums[i] == nums[i-1]);
                    while (i < --j && nums[j] == nums[j+1]);
                }
            }
        }
        return tri;
    }
};

}  /* namespace solution_015 */
